import java.util.*;

/**
 * Created by L.jp
 * Description:给出一个有n个点，m条有向边的图，你可以施展魔法把一条有向边变成无向边，问1到n的最短路,
 * 如果1不能到n，输出-1.
 * 使用python的考生请用pypy提交!否则可能超时。
 *
 * 输入描述;
 * 第一行输入两个整n,m。(1<n≤10^5,1<=m≤2×105)
 * 接下来m行,每行输入三个整数x,y,z，表示x到y ﹒条边权为z的有向边。(1≤x,y<=n,1<z<10^8)
 * 输出描述;
 * 输出一行一个整数表示答案。
 * 示例1输入输出示例仅供调试,后台判题数据一般不包含示例
 * 输入
 * 43
 * 122
 * 134
 * 236
 * 输出-1
 *
 * 说明
 * 无论怎么施展魔法,1都没法到n
 * User: 86189
 * Date: 2023-04-08
 * Time: 0:16
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<int[]>[] graph = new List[n+1]; // 用邻接表存储图
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            graph[x].add(new int[]{y, z}); // 添加有向边
        }
        int[] dist = new int[n+1]; // 存储最短路
        Arrays.fill(dist, Integer.MAX_VALUE); // 初始化为无穷大
        dist[1] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); // 优先队列存储待处理的点
        pq.offer(new int[]{1, 0});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int node = cur[0];
            int distance = cur[1];
            if (distance > dist[node]) { // 如果当前点已经被处理过，则跳过
                continue;
            }
            for (int[] next : graph[node]) { // 遍历当前点的邻居节点
                int neigh = next[0];
                int weight = next[1];
                if (dist[neigh] > dist[node] + weight) { // 如果可以松弛，则更新最短路
                    dist[neigh] = dist[node] + weight;
                    pq.offer(new int[]{neigh, dist[neigh]});
                }
            }
        }
        System.out.println(dist[n] == Integer.MAX_VALUE ? -1 : dist[n]); // 如果1到n不连通，则输出-1
    }
}